package developer.算法.二叉树.二叉树直径;

/**
 * @author zhangyongkang
 * @time 2025/3/24 17:16
 * @description 给你一棵二叉树的根节点，返回该树的 直径 。
 * <p>
 * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
 * <p>
 * 两节点之间路径的 长度 由它们之间边数表示。
 */
public class ErChaShuDeZhiJing {

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */

    static class Solution3 {
        int ans = 1;

        public int diameterOfBinaryTree(TreeNode root) {
            ans = 1;
            dfs(root);
            return ans;
        }

        private int dfs(TreeNode root) {
            if (root == null) return 0;
            int left = dfs(root.left);
            int right = dfs(root.right);
            ans = Math.max(ans, left + right + 1);
            return Math.max(left, right) + 1;
        }
    }

    static class Solution {
        int ans = 1;

        //左侧最长节点+右侧最长节点+1
        public int diameterOfBinaryTree(TreeNode root) {
            ans = 1;
            deep(root);
            return ans;
        }

        public int deep(TreeNode root) {
            if (root == null) return 0;
            int left = deep(root.left);
            int right = deep(root.right);
            ans = Math.max(ans, left + right + 1);
            return Math.max(left, right) + 1;

        }


    }


    static class SolutionOfficial {
        int ans;

        public int diameterOfBinaryTree(TreeNode root) {
            ans = 1;
            depth(root);
            return ans - 1;
        }

        public int depth(TreeNode node) {
            if (node == null) {
                return 0; // 访问到空节点了，返回0
            }
            int L = depth(node.left); // 左儿子为根的子树的深度
            int R = depth(node.right); // 右儿子为根的子树的深度
            ans = Math.max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
            return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
        }
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
